1. Technical Field
The invention relates generally to wireless communication systems and, more particularly, to error detection methods for evaluating information that is transmitted in control channels of such systems.
2. Description of Related Art
Almost all wireless communication systems employ “frame-based” communication, where a certain number of bits, defined as a frame, are channel encoded together and transmitted. Most systems employ concatenated coding for each frame with an inner error correction code such as a convolutional or Turbo error correction code and an outer error detection code.
FIG. 1 illustrates a process flow for forming a typical concatenated code structure at the transmitter of a base station. As shown, an error detection code is added at 110 to a frame of a data channel, the frame comprising k bits. Typically a cyclic redundancy check (CRC) code, shown here as having a length p, is used as the error detection code. The CRC bits are computed based on the k information bits . The CRC code is appended to the frame (e.g., k+p bits), and then passed through error correction encoding at 120. The error correction code is, for example, a convolutional code having a rate of 1/r, where r>1. After error correction encoding, the number of bits equals (r*(k+p)), which are then passed to a modulator and transmitted over a channel. An error correction code decoder at the receiver of a user equipment (e.g., a mobile station) will attempt to correct any bit errors that take place on the channel.
In most cases, a frame is discarded when the receiver detects an error, which is uncorrectable, in the transmission based on the error detection code. This results in a loss or delay of information, depending on whether a retransmission is subsequently carried out. The most widely used error detection code is the aforementioned CRC code. Standard CRC codes include bit lengths of 8, 12, 16, 24 and/or 32 bits. The figure of merit or interest with error detection codes is the probability of an undetected error, i.e., a case where use of the inner error correction code could not correct transmission errors, and the outer error detection code did not detect that the decoded information was erroneous. This is an undetected error because the decoded information is erroneous, but the error detection code did not catch the error. The undetected error probability with CRC codes is typically on the order of 2−L where L is the length of the CRC. Thus, an 8-bit CRC has an undetected error probability of approximately 1/256.
The overhead associated with using a CRC is dependent on the number of information bits in the frame. Typically, the number of information bits of a frame such as frame k in FIG. 1 exceeds several hundred bits, and thus any overhead effect of using an 8, 12 or 16-bit CRC is minimal. However, in certain applications very few bits need to be transmitted per frame and the overhead from using even a length-8 CRC may be excessive. One such example is in the transmission of control channel information in wireless high speed data communication systems such as in the High Speed Downlink Packet Access (HSDPA) specification of the Universal Mobile Telecommunication System (UMTS) standard.
In HSDPA, transmission data for several user equipments (hereinafter UEs, also frequently known as mobile stations) are multiplexed on a common high speed downlink shared data channel (HS-DSCH). High data rates are obtained through scheduling, adaptive modulation and coding, and hybrid automatic repeat request (H-ARQ) as is known. UEs are scheduled on the shared data channel. The UEs are scheduled either in a purely time division multiplexed (TDM) manner, where all the available resources (power resources and data channelization codes) are assigned to one UE during a transmission time interval, or among multiple UEs in a transmission time interval (TTI). When transmitting to multiple UEs in a TTI, the power resources and data channelization codes are divided up among those UEs, not necessarily in a uniform manner. In the UMTS standard, the transmission time interval (TTI) is typically 2 ms or 3 timeslots (each timeslot being about 0.667 ms). Scheduling for the UEs is typically accomplished based on some type of information about the channel quality being experienced by the UE.
An important component of these high speed wireless systems is the use of a control channel. The control channel carries information related to (a) which UEs have been scheduled to receive a data transmission via a corresponding HS-DSCH (b) what data channel codes, are assigned to each particular UE, and (c) modulation and HARQ-related information. From a system efficiency perspective, a few control channels are defined such that they are shared among all UEs, rather than providing a dedicated control channel per UE.
An exemplary configuration is to define up to M high speed shared control channels (HS-SCCHs) for simultaneous transmissions, where M=4, for example. For each TTI, each HS-SCCH carries HS-DSCH-related downlink signaling for one UE. The number of HS-SCCHs may range from a minimum of one HS-SCCH (M=1) to a maximum of four HS-SCCH's (M=4). This is the number of HS-SCCH's as seen from the UE's point-of-view. In other words, a UE determines whether an ensuing transmission on any of the HS-DSCHs is intended for itself or not only upon or after decoding information in the HS-SCCHs.
FIG. 2 illustrates the relationship between HS-SCCHs 210 and their corresponding shared HS-DSCH counterparts 220. In FIG. 2, each HS-SCCHx (x=1 to 4) carries information pertinent to a corresponding HS-DSCHx (x=1 to 4). The number of HS-DSCHs, and therefore the number of HS-SCCHs that may be used, can vary for each TTI, depending on the number of UEs being simultaneously scheduled in the TTI. Accordingly, the configuration of HS-SCCHs and HS-DSCHs in FIG. 2 enables the data channelization codes and power resources to be divided among four simultaneous transmissions.
Referring again to FIG. 2, control channel data on each HS-SCCH is typically divided into two parts. Part I consists of information relating to those data channelization codes that have been assigned to a particular UE, for example. Part II data contains HARQ related information, and other transport information. To maintain complexity low at the UE, HS-SCCH designs typically allow Part I information to be transmitted prior to the commencement (i.e., before t=0) of data transmission, as shown in FIG. 2. Accordingly, with the current configuration, each UE must decode Part I on every HS-SCCH, in every TTI, in order to determine (a) whether or not the transmission was intended for that particular UE, and (b) if the transmission was intended for that particular UE, the UE must decode Part I and figure out what channelization codes the corresponding HS-DSCH will arrive on.
Therefore, each UE must decode up to four (4) HS-SCCHs in every TTI, prior to commencement of data transmission. From a UE processing complexity perspective, it is therefore desirable to limit the number of bits in Part I that require processing, and it is also desirable that the processing be as simple as possible. At the same time, two conditions should be met for each UE. The first is that at each UE, the probability of error detection should be high. In other words, when a transmission is intended for a particular UE, that UE decodes Part I and successfully recognizes that the ensuing data transmission on the corresponding HS-DSCH is for that UE. The second condition to meet is for a probability of false alarm to be low. A false alarm is where a UE decodes Part I and erroneously recognizes that the ensuing data transmission on a corresponding HS-DSCH is for that UE.
A low probability of detection implies wasted resources, since every missed detection event means that the transmission on the corresponding HS-DSCH is wasted. A false alarm event would cause a UE that is NOT scheduled for a particular transmission to begin buffering data and try to decode the information which would waste battery resources at the UE, for example, due to unnecessary processing.
In order to ensure the above two conditions are met, typically a UE-specific CRC code is used for error detection on Part I. Accordingly, the UE will decode Part I bits and apply its unique CRC to check for errors. If there are errors, the UE will assume that the transmission is not intended for it. If use of the CRC detects no errors on Part I of the HS-SCCHs, the UE will decode Part II of the HS-SCCH and begin to buffer and decode the corresponding HS-DSCH.
Standard CRC codes having bit lengths of 12 bits or higher usually achieve acceptable detection/false alarm performance. However, Part I of the HS-SCCH usually contains only about 8 information bits, so to use a 12-bit CRC or greater represents a substantial overhead (>150%). Furthermore, the number of Part I bits the UE must process is excessive. For example, for each HS-SCCH having 8 information bits and 12 CRC bits, in order to decode the Part I information for four HS-SCCHs, the UE has to process 80 bits of data, typically within 1 timeslot of a TTI (0.667 ms). This is undesirable, and is essentially the equivalent of processing a peak data rate of 120 kbps just to decode part of the control information
A conventional solution is to avoid using a CRC for error detection, and instead use a UE-specific scrambling or masking approach followed by calculation of a specific convolutional decoder metric for error detection that is described in further detail below. The principle behind this approach is that when the UE descrambles a transmission that is intended for itself, the resultant decoder metric is usually high. However, whenever the UE descrambles a transmission that was intended for some other UE, the decoder metric is usually low. Therefore, scrambling/descrambling to calculate a decoder metric, followed by comparison of the decoder metric to a threshold is one method to achieve error detection when no CRC is used.
FIG. 3 illustrates a process flow of how a scrambling code is used with a convolutional error correction code. The UE-specific scrambling (masking) code “flips” certain bits (1 to 0 and 0 to 1) based on the unique scrambling sequence assigned to the UE.
For example, in FIG. 3 suppose the scrambling sequence in block 320 is 0101 and the output bits from the convolutional code in block 310 are 1101, If the scrambling code flips the output bits, then the sequence after scrambling will be 1000. When the UE decodes this sequence, the UE will invert the scrambling using its own sequence, and then pass the resulting information through a convolutional decoder. The effect of this scrambling is that when the transmission is not intended for the UE, path metrics calculated using a Viterbi decoding algorithm of the convolutional code are quite low. A discussion of the Viterbi algorithm, which is utilized by the above-mentioned UE-specific scrambling or masking approach to error detection, as well as a discussion of path metrics follows.
Viterbi Algorithm
The Viterbi algorithm for convolutional decoding is a known decoding algorithm that is optimum in the sense that it yields the maximum likelihood (ML) or most likely sequence of bits based on using the output values from the channel. Viterbi decoding is the standard technique to decode convolutional codes regardless of whether a CRC is used or not. A description of the Viterbi algorithm for decoding convolutional codes may be found in a standard communications textbook such as ‘Digital Communications” by J. G. Proakis, 2nd Edition, McGraw Hill. Some of the concepts are repeated briefly below for convenience.
A convolutional encoder comprises a number of shift registers or memory elements. The number of shift registers is called the constraint length of the code, and each shift register stores exactly 1 bit of information. Each time a new bit comes in, it is read into a leftmost shift register location and the contents of each shift register are shifted to the shift register on the immediate right. The contents of the rightmost shift register are obviously thrown out. Thus, a convolutional encoder may be viewed as a linear filter that operates on bits.
A convolutional encoder is also characterized by a code rate. In general, the code rate defines how many output bits are produced for every input bit. Therefore a code rate of 1/r implies that for every information bit inputted, r coded bits are output by the encoder. Thus, the larger the value of r, the more powerful the code (i.e. the greater its ability to correct transmission errors). Finally, how the r output bits are produced needs to be specified; this is given by the connections of shift register elements to exclusive-OR elements.
FIG. 4 is a state diagram of a simple convolutional encoder 400. Convolutional encoder 400 has a constraint length k=3 and a rate=½, as is known. The constraint length defines the number of shift-register elements that are used. The shift register elements are part of a memory or shift register in the UE. In FIG. 4, there are three shift register elements 410, 420 and 430. Shift register element 410 will contain the most recently inserted information bit. Each time a new information bit comes in, the previous bits are shifted to the right, so the middle element 420 contains the next-to-most-recent bit and the right most element 430 contains the third most recent bit (e.g., least recent bit). XOR operations at 440 and 450 determine how the coded bits are determined. Each time an information bit 415 is input, two coded bits 445 and 455 are output, as shown in FIG. 4.
FIG. 5 illustrates a trellis diagram 500 to explain how the Viterbi algorithm, and specifically Viterbi decoding, is implemented at the UE. States in the trellis, represented by black dots in FIG. 5, denote the four possible shift register contents (00, 01, 10 or 11, shown along the left-hand side of the trellis diagram) when a bit comes in. Therefore for binary convolutional codes, the number of states is 2constraint length−1, or 2k−1. For each information bit inputted, the center shift register element 420 and rightmost element 430 would therefore be at a state of 00, 01, 11 or 10, depending on the state of the previous two information bits that have been shifted right. The first bit in the state is defined as the least recent bit (contents of the rightmost shift register 430) and the second bit (contents of the middle shift register 420) is defined as the next least recent bit. So if the previous two bits were 1 and 0, then the state will be 01.
The trellis diagram is provided for the convolutional coding shown in FIG. 4, and is drawn for seven (7) levels (levels represented by J, where J=1 to 7) corresponding to 7 information bits The trellis diagram in FIG. 5 assumes that two (2) tail bits are used to terminate the trellis and return the decoder back to the state 00. In general, the number of tail bits required would be equal to the constraint length minus 1 (k−1).
Each level J (J=1 to 7) across the top of the trellis diagram in FIG. 5 corresponds to each information bit. Prior to inputting the first bit, the two shift register elements 420 and 430 are always set to 0, so the starting state at level J=0 is always 00. If the first information bit is a 0, then at level J=1 the decoder remains at state 00. On the other hand, if the first information bit into decoder 400 at J=0 is a 1, then the decoder 400 moves to state 01 at level J=1. Each possible transition from one level to the next is called a branch. A sequence of connected branches is called a path through the trellis.
The Viterbi algorithm proceeds by computing what is termed a “branch metric” at each J level. The branch metric is obtained by “correlating” the received bits from the channel with the bits that would have been sent if that branch were taken as the correct channel for the UE. The higher the correlation, the more likely the branch was the correct one. So, in an example where the actual bits received from the channel for a particular J level are 10, then any branch that would have produced a branch metric of 10 at that J level has the highest correlation.
Branch metrics from previous J levels are summed to yield what is called a path metric. The higher the value of the path metric, the more likely that the path metric corresponds to the actual transmitted sequence of bits. Two paths will merge at every state in the trellis and at every level. Viterbi decoding therefore entails comparing the path metrics of the two merging or competing paths and discarding the one with the worse (lowest valued) path metric. Occasionally, due to noise, the incorrect path is chosen over the correct one during one of the aforementioned merging instances. This results in a decoding error. Accordingly, the path that is selected by the Viterbi algorithm is called the survivor or winning path.
There is at most one winning path per state, per level. Since tail bits are used, the state at the last level will always be an all-zero state. In the example, 2 tail bits are used and the state at the last level is 00. As stated before, two paths will merge at the 00 state at the last level. Accordingly, the Viterbi decoding algorithm selects the path with the larger path metric at this last (J=7) level. This path now is the eventual winning path and represents the “most likely” sequence of transmitted bits.
Accordingly, in the scrambling approach where no CRC is used for error detection, error detection is performed using Viterbi decoding with the scrambling approach. In this context, the conventional method is to determine a path metric difference between the merging paths in the last level (e.g. J=7 in the trellis diagram of FIG. 5). If that calculated path metric difference is below a predetermined threshold, then the decoding is considered unreliable, and the UE declares that the transmission on that particular HS-SCCH was not intended for it. This is termed an End Path Metric Difference (EPMD) approach to error detection. The EPMD approach avoids transmission of CRC bits and thus lowers the processing requirement at the UE.